/*
[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/*
思路：
1.初始化：创建一个哨兵位头节点newhead，指针cur指向newhead
2.循环合并：当l1或l2为空时跳出
  a. l1->val < l2->val时；cur->next指向节点l1，并且l1向前走一步
  b. l1->val >= l2->val时，cur->next指向l2，并且l2向前走一步
  c. cur向前走一步
3.合并剩余尾部：上述循环跳出时，有两种情况，l1为空或l2为空
  a. 若l1 != 空时，将l1添加到节点cur之后
  b. 否则：将l2添加到cur节点之后
4. 返回：返回newhead->next
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = newhead;
    while(list1 && list2)
    {
        if(list1->val < list2->val){
            cur->next = list1;
            list1 = list1->next;
        }else{
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    cur->next = list1 == NULL ? list2 : list1;

    return newhead->next;
}